#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣658. 找到 K 个最接近的元素
// 【难度】中等
// 【提交】https://leetcode.cn/problems/find-k-closest-elements/submissions/677438764/
// 【标签】二分查找；双指针；滑动窗口
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int n = arr.size();
    int left = 0, right = n - 1;
    while (right - left >= k) {
        if (x - arr[left] <= arr[right] - x)right--;
        else left++;
    }
    return vector<int>(arr.begin() + left, arr.begin() + left + k);
    }
};

/**
 * @brief 学习总结：
 * 本题要求找到数组中k个最接近x的元素，并保持原数组顺序。
 * 
 * 解题思路：
 * 1. 使用双指针从数组两端向中间移动
 * 2. 比较左右指针与x的距离，移动距离较大的指针
 * 3. 当窗口大小恰好为k时停止，返回该窗口内的元素
 * 
 * 算法分析：
 * - 时间复杂度：O(n-k)，每次循环排除一个元素，直到剩下k个元素
 * - 空间复杂度：O(1)，除了返回结果外不需要额外空间
 * 
 * 优点：
 * - 双指针思路巧妙，代码简洁高效
 * - 利用数组已排序的特性，保证结果的有序性
 * - 直接返回原数组的连续片段，无需额外排序
 * 
 * 改进建议：
 * 1. 使用二分查找优化，找到最优起始位置：
 * 
 * vector<int> findClosestElements(vector<int>& arr, int k, int x) {
 *     int left = 0, right = arr.size() - k;
 *     while (left < right) {
 *         int mid = left + (right - left) / 2;
 *         if (x - arr[mid] > arr[mid + k] - x) {
 *             left = mid + 1;
 *         } else {
 *             right = mid;
 *         }
 *     }
 *     return vector<int>(arr.begin() + left, arr.begin() + left + k);
 * }
 * 
 * 2. 时间复杂度优化为O(log(n-k) + k)
 * 
 * 3. 考虑边界情况：
 *    - 当x小于所有元素时，返回前k个
 *    - 当x大于所有元素时，返回后k个
 *    - 当k等于数组长度时，返回整个数组
 * 
 * 核心思想：
 * 利用数组的有序性，通过排除法确定最优的k个连续元素。
 * 关键观察：最接近x的k个元素在排序数组中一定是连续的。
 * 
 * 距离比较逻辑：
 * - 如果x - arr[left] <= arr[right] - x，说明arr[left]比arr[right]更接近或相等
 * - 此时移动右指针，因为保留arr[left]可能更优
 * - 反之移动左指针
 * 
 * 应用场景：
 * - 在有序数组中查找最接近的k个元素
 * - 数据过滤和近似查询
 * - 推荐系统中的相似项查找
 */